//题目:
// 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
// 每步 可以删除任意一个字符串中的一个字符。

// 示例 1：
// 输入: word1 = "sea", word2 = "eat"
// 输出: 2
// 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

// 示例  2:
// 输入：word1 = "leetcode", word2 = "etco"
// 输出：4
 
// 提示：
// 1 <= word1.length, word2.length <= 500
// word1 和 word2 只包含小写英文字母
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int minDistance(string word1, string word2) 
    {
        //题意转换：找出word1和word2的最长公共子序列的长度
        int m=word1.size(),n=word2.size();
        //1.创建dp表————dp[i][j]表示：word1中[0,i]子串与word2中[0,j]子串的最长公共子序列长度
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2.初始化————暂无
        //3.填表————动态转移方程:dp[i][j]
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1]==word2[j-1]) dp[i][j]=1+dp[i-1][j-1];
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
        //4.确定返回值
        return m+n-2*dp[m][n];
    }
};